package basis.netease.hard;

import java.util.LinkedList;
import java.util.Scanner;

/**
 * 7-5 二叉树的最大路径和
 * 二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
 * 路径和 是路径中各节点值的总和。
 * 给你一个二叉树的根节点 root ，返回其 最大路径和 。
 * 输入格式:
 * 树上的节点数满足 0 <= n <= 1000, 每个节点的值满足 -1000 <= val <= 1000
 * （注：null节点的左右叶子不会再打印null）
 * 输出格式:
 * 输出最大路径的和
 * 输入样例:
 * 在这里给出一组输入。例如：
 * -10,9,20,null,null,15,7
 * 输出样例:
 * 在这里给出相应的输出。例如：
 * 42
 */
public class Main_5 {
    private static int maxSum = Integer.MIN_VALUE;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        TreeNode root = buildTree(input.split(","));
        calculateSum(root);
        System.out.println(maxSum);
    }

    public static TreeNode buildTree(String[] nums) {
        if ("null".equals(nums[0])) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(nums[0]));
        LinkedList<TreeNode> queue = new LinkedList();
        queue.offerLast(root);
        int i = 1;
        while (!queue.isEmpty() && i < nums.length) {
            TreeNode currentNode = queue.pollFirst();
            if (!"null".equals(nums[i])) {
                TreeNode leftNode = new TreeNode(Integer.parseInt(nums[i]));
                currentNode.left = leftNode;
                queue.offerLast(leftNode);
            }
            i++;
            if (i < nums.length && !"null".equals(nums[i])) {
                TreeNode rightNode = new TreeNode(Integer.parseInt(nums[i]));
                currentNode.right = rightNode;
                queue.offerLast(rightNode);
            }
            i++;
        }
        return root;
    }

    private static int calculateSum(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int sumL = calculateSum(node.left);
        // 如果是负数，直接不要这个子节点，按0处理
        sumL = Math.max(0, sumL);
        int sumR = calculateSum(node.right);
        sumR = Math.max(0, sumR);
        maxSum = Math.max(maxSum, node.value + sumL + sumR);
        // 取左右节点中最大的节点
        return Math.max(sumL, sumR) + node.value;
    }

    public static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;

        public TreeNode(int value) {
            this.value = value;
        }
    }

}
